import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 18:05
 * @description 完全背包问题，但是求的是方案数，
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        // f[i]表示面额为 i的组合数
        int[] f = new int[cnt + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // 面额为 val
            int val = cs[i - 1];
            // 完全背包问题，f[j] 为 上一行的f[j] + 这一行的f[j-val]总和，依赖这一行f[j-val]，因此需要从小往大遍历
            for (int j = val; j <= cnt; j++) {
                f[j] += f[j - val];
            }
        }
        return f[cnt];
    }
}
